﻿public class MyLinkedList
{

    public int val;
    public MyLinkedList next;
    public MyLinkedList prev;
    private int length = 0;
    public MyLinkedList()
    {
        this.val = 0;
        this.next = this;
        this.prev = this;
    }
    
    public MyLinkedList(int val)
    {
        this.val = val;
        this.next = this;
        this.prev = this;
    }
    
    public int Get(int index) {
        if (index < 0 || index >= this.length)
        {
            return -1;
        }
        MyLinkedList node = this;
        for (int i = 0; i <= index; i++)
        {
            node = node.next;
        }

        return node.val;
    }
    
    public void AddAtHead(int val)
    {
        MyLinkedList h = new MyLinkedList(val);
        h.next = this.next;
        h.prev = this;
        this.next.prev = h;
        this.next = h;
        this.length++;
    }
    
    public void AddAtTail(int val) {
        MyLinkedList t = new MyLinkedList(val);
        t.next = this;
        t.prev = this.prev;
        this.prev.next = t;
        this.prev = t;
        this.length++;
    }
    
    public void AddAtIndex(int index, int val) {
        if (index > this.length) // 不插入
        {
            return;
        }
        else if (index == this.length) // 插入到末尾
        {
            this.AddAtTail(val);
        }
        else if (index <= 0) // 插入到头部
        {
            this.AddAtHead(val);
        }
        else
        {
            // 找到前缀节点
            MyLinkedList pre = this;
            for (int i = 0; i < index; i++)
            {
                pre = pre.next;
            }
            
            // 插入节点
            MyLinkedList n = new MyLinkedList(val);
            n.prev = pre;
            n.next = pre.next;
            pre.next.prev = n;
            pre.next = n;
            this.length++;
        }
        
    }
    
    public void DeleteAtIndex(int index) {
        if (index < 0 || index >= this.length)
        {
            return;
        }
        // 找到前一个节点
        MyLinkedList pre = this;
        for (int i = 0; i < index; i++)
        {
            pre = pre.next;
        }

        pre.next = pre.next.next;
        pre.next.prev = pre;
        this.length--;

    }
}
public class Solution {

    public static void Main(string[] args)
    {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.AddAtHead(1);
        myLinkedList.AddAtTail(3);
        myLinkedList.AddAtIndex(1, 2);    // 链表变为 1->2->3
        int i = myLinkedList.Get(1);              // 返回 2
        myLinkedList.DeleteAtIndex(1);    // 现在，链表变为 1->3
        int j = myLinkedList.Get(1);              // 返回 3
        Console.WriteLine(i);
        Console.WriteLine(j);
    }
}